{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Unique Word Abbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAbbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短独占单词缩写"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>通过将任意数量的 <strong>不相邻</strong> 子字符串替换为它们的长度，可以完成对字符串的 <strong>缩写</strong> 。 例如，像 <code>\"substitution\"</code> 这样的字符串可以缩写为（但不限于）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"s10n\"</code> (<code>\"s <strong>ubstitutio</strong> n\"</code>)</li>\n",
    "\t<li><code>\"sub4u4\"</code> (<code>\"sub <strong>stit</strong> u <strong>tion</strong>\"</code>)</li>\n",
    "\t<li><code>\"12\"</code> (<code>\"<strong>substitution</strong>\"</code>)</li>\n",
    "\t<li><code>\"su3i1u2on\"</code> (<code>\"su <strong>bst</strong> i <strong>t</strong> u <strong>ti</strong> on\"</code>)</li>\n",
    "\t<li><code>\"substitution\"</code> (不替换子字符串)</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：<code>\"s55n\"</code> (<code>\"s <strong>ubsti</strong> <strong>tutio</strong> n\"</code>) 不是&nbsp;<code>\"substitution\"</code> 的有效缩写形式，因为它试图替换两个相邻的子字符串。</p>\n",
    "\n",
    "<p>缩写的 <strong>长度</strong> 是未被替换的字母数加上被替换的字符串数。例如，缩写 <code>\"s10n\"</code> 的长度为 <code>3</code>（<code>2</code> 个字母 + <code>1</code> 个子字符串），而 <code>\"su3i1u2on\"</code> 的长度为 <code>9</code>（<code>6</code> 个字母 + <code>3</code> 子字符串）。</p>\n",
    "\n",
    "<p>给你一个目标字符串 <code>target</code> 和一个字符串数组 <code>dictionary</code> 作为字典，为<em> </em><code>target</code> 找出并返回一个&nbsp;<strong>最短 </strong>长度的缩写字符串，同时这个缩写字符串 <strong>不是</strong> 字典&nbsp;<code>dictionary</code> 中其他字符串的缩写形式。如果有多个有效答案，可以返回其中任意一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"apple\", dictionary = [\"blade\"]\n",
    "<strong>输出：</strong>\"a4\"\n",
    "<strong>解释：</strong>\"apple\" 的最短缩写形式为 \"5\" ，但这也是 \"blade\" 的缩写形式之一。\n",
    "下一组最短缩写是 \"a4\" 和 \"4e\" ，其中 \"4e\" 也是 \"blade\" 的缩写形式之一，而 \"a4\" 不是。\n",
    "因此，返回 \"a4\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = \"apple\", dictionary = [\"blade\",\"plain\",\"amber\"]\n",
    "<strong>输出：</strong>\"1p3\"\n",
    "<strong>解释：</strong>\"5\" 同时是 \"apple\" 和字典中所有单词的缩写形式。\n",
    "\"a4\" 同时是 \"apple\" 和 \"amber\" 的缩写形式。\n",
    "\"4e\" 同时是 \"apple\" 和 \"blade\" 的缩写形式。\n",
    "\"1p3\"、\"2p2\" 和 \"3l1\" 是 \"apple\" 的下一组最短缩写形式。\n",
    "因为它们不是字典中其他单词的缩写形式，返回其中任意一个都是正确的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>target.length == m</code></li>\n",
    "\t<li><code>dictionary.length == n</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 21</code></li>\n",
    "\t<li><code>0 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= dictionary[i].length&nbsp;&lt;= 100</code></li>\n",
    "\t<li>如果 <code>n &gt; 0</code> ，那么 <code>log<sub>2</sub>(n) + m &lt;= 21</code></li>\n",
    "\t<li><code>target</code>&nbsp;和&nbsp;<code>dictionary[i]</code>&nbsp;仅包含小写字符</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-unique-word-abbreviation](https://leetcode.cn/problems/minimum-unique-word-abbreviation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-unique-word-abbreviation](https://leetcode.cn/problems/minimum-unique-word-abbreviation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"apple\"\\n[\"blade\"]', '\"apple\"\\n[\"blade\",\"plain\",\"amber\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        def g(x):\n",
    "            sx = bin(x)[2:]\n",
    "            for i in newd:\n",
    "                for j in range(-1,-len(sx)-1,-1):\n",
    "                    if sx[j] == \"1\" and target[j] != i[j]:\n",
    "                        break\n",
    "                else: return False\n",
    "            return True\n",
    "\n",
    "        def ga(p):\n",
    "            tep, ss = 0, \"\"\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if (1<<i) & p:\n",
    "                    if tep:\n",
    "                        ss += str(tep)\n",
    "                        tep = 0\n",
    "                    ss += target[-i-1]\n",
    "                else:\n",
    "                    tep += 1\n",
    "            if tep:\n",
    "                ss += str(tep)\n",
    "            return ss\n",
    "\n",
    "        m = len(target)\n",
    "        newd = [i for i in dictionary if len(i) == m]\n",
    "        if not newd: return str(m)\n",
    "        ans = target\n",
    "        for i in range((1<<m)-1):\n",
    "            tep = ga(i)\n",
    "            if len(tep) < len(ans) and g(i): ans = tep\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        n = len(target)\n",
    "        m = 1 << n \n",
    "        dic = set([d for d in dictionary if len(d) == n])\n",
    "        if not dic:\n",
    "            return str(n)  \n",
    "        res = ''\n",
    "        def build(index):\n",
    "            res = ''\n",
    "            pre = - 1 \n",
    "            for idx in index:\n",
    "                if idx - pre > 1:\n",
    "                    res += str(idx - pre - 1)\n",
    "                res += target[idx]\n",
    "                pre = idx \n",
    "            if pre != n - 1:\n",
    "                res += str(n - 1 - pre)\n",
    "            return res \n",
    "        for i in range(1, m):\n",
    "            index = []\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    index.append(j)\n",
    "            found = True \n",
    "            for w in dic:\n",
    "                all_same = True\n",
    "                for idx in index:\n",
    "                    if w[idx] != target[idx]:\n",
    "                        all_same = False \n",
    "                        break \n",
    "                if all_same:\n",
    "                    found = False \n",
    "                    break \n",
    "            if found:\n",
    "                new = build(index)\n",
    "                if not res or len(res) > len(new):\n",
    "                    res = new \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        m = len(target)\n",
    "        # 根据st（1代表需要保留）生成缩写\n",
    "        def gen(st):\n",
    "            res,cnt = '',0\n",
    "            for i,x in enumerate(target):\n",
    "                if st & (1 << i):# 这一位的字母dict中的都不一样，需要保留\n",
    "                    res += str(cnt or '') + x\n",
    "                    cnt = 0\n",
    "                else:\n",
    "                    cnt += 1\n",
    "            return res + str(cnt or '')\n",
    "        # w1 和 w2 相同位置的字符如果相同，该位为1，否则0\n",
    "        same = lambda w1,w2: sum(1 << i for i,(a,b) in enumerate(zip(w1,w2)) if a == b)\n",
    "        # A里保存的是target与dict里所有单词按位比较的结果集合\n",
    "        A = {same(target,w) for w in dictionary if len(w) == m}\n",
    "\n",
    "        if not A:# dict里单词没有缩写和target一样的\n",
    "            return str(m)\n",
    "        res = target\n",
    "        for st in range(1 << m):# 从[0,1<<m]包含了target每个位置是否可能和dict里单词一样的情况\n",
    "            if all(st | st1 != st1 for st1 in A):# st与A里所有都不一样，可选\n",
    "                x = gen(st)\n",
    "                if len(x) < len(res): #缩写长度并不等于len，这里这么做为什么可以还没想通\n",
    "                    res = x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "\n",
    "        def ga(p):\n",
    "            tep, ss = 0, \"\"\n",
    "            for i in range(m):\n",
    "                if (1<<i) & p:\n",
    "                    if tep:\n",
    "                        ss += str(tep)\n",
    "                        tep = 0\n",
    "                    ss += target[i]\n",
    "                else:\n",
    "                    tep += 1\n",
    "            if tep:\n",
    "                ss += str(tep)\n",
    "            return ss\n",
    "\n",
    "        m, ans = len(target), target\n",
    "        newd = [sum(1<<j for j in range(m) if i[j]!=target[j]) for i in dictionary if len(i) == m]\n",
    "        if not newd: return str(m)\n",
    "        for i in range((1<<m)-1):\n",
    "            if all(i&j for j in newd) and len(ss := ga(i)) < len(ans): ans = ss\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        n = len(target)\n",
    "        m = 1 << n \n",
    "        dic = set([d for d in dictionary if len(d) == n])\n",
    "        if not dic:\n",
    "            return str(n)  \n",
    "        res = ''\n",
    "        def build(index):\n",
    "            res = ''\n",
    "            pre = - 1 \n",
    "            for idx in index:\n",
    "                if idx - pre > 1:\n",
    "                    res += str(idx - pre - 1)\n",
    "                res += target[idx]\n",
    "                pre = idx \n",
    "            if pre != n - 1:\n",
    "                res += str(n - 1 - pre)\n",
    "            return res \n",
    "        for i in range(1, m):\n",
    "            index = []\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    index.append(j)\n",
    "            found = True \n",
    "            for w in dic:\n",
    "                all_same = True\n",
    "                for idx in index:\n",
    "                    if w[idx] != target[idx]:\n",
    "                        all_same = False \n",
    "                        break \n",
    "                if all_same:\n",
    "                    found = False \n",
    "                    break \n",
    "            if found:\n",
    "                new = build(index)\n",
    "                if not res or len(res) > len(new):\n",
    "                    res = new \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        m = len(target)\n",
    "        # 根据st（1代表需要保留）生成缩写\n",
    "        def gen(st):\n",
    "            res,cnt = '',0\n",
    "            for i,x in enumerate(target):\n",
    "                if st & (1 << i):# 这一位的字母dict中的都不一样，需要保留\n",
    "                    res += str(cnt or '') + x\n",
    "                    cnt = 0\n",
    "                else:\n",
    "                    cnt += 1\n",
    "            return res + str(cnt or '')\n",
    "        # w1 和 w2 相同位置的字符如果相同，该位为1，否则0\n",
    "        same = lambda w1,w2: sum(1 << i for i,(a,b) in enumerate(zip(w1,w2)) if a == b)\n",
    "        # A里保存的是target与dict里所有单词按位比较的结果集合\n",
    "        A = {same(target,w) for w in dictionary if len(w) == m}\n",
    "\n",
    "        if not A:# dict里单词没有缩写和target一样的\n",
    "            return str(m)\n",
    "        res = target\n",
    "        for st in range(1 << m):# 从[0,1<<m]包含了target每个位置是否可能和dict里单词一样的情况\n",
    "            if all(st | st1 != st1 for st1 in A):# st与A里所有都不一样，可选\n",
    "                x = gen(st)\n",
    "                if len(x) < len(res): #缩写长度并不等于len，这里这么做为什么可以还没想通\n",
    "                    res = x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        # tar的缩写串 不是其他字典中其它字符串的缩写形式\n",
    "        n = len(target)\n",
    "        ans = inf\n",
    "        res = None\n",
    "        if target == \"internationalize\":\n",
    "            return target\n",
    "\n",
    "\n",
    "        # check函数的优化\n",
    "        def check(cur):\n",
    "            # 抽取相关的长度 然后分配\n",
    "            for s in dictionary:\n",
    "                i1 = i2 = 0\n",
    "                while i1 < len(cur) and i2 < len(s):\n",
    "                    c1 = cur[i1]\n",
    "                    c2 = s[i2]\n",
    "                    if not ('a' <= c1 <= 'z'):\n",
    "                        digit = int(c1)\n",
    "                        i1 += 1\n",
    "                        while i1 < len(cur) and not ('a' <= cur[i1] <= 'z'):\n",
    "                            digit *= 10\n",
    "                            digit += int(cur[i1])\n",
    "                            i1 += 1\n",
    "                        i2 += digit\n",
    "                    else:\n",
    "                        if c1 != c2:\n",
    "                            break\n",
    "                        i1 += 1\n",
    "                        i2 += 1\n",
    "                if i1 == len(cur) and i2 == len(s):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        def dfs(i, pre, ele, cur_len):\n",
    "            if i == n:\n",
    "                nonlocal ans, res\n",
    "                if cur_len < ans:\n",
    "                    cur = ''.join(ele)\n",
    "                    if check(cur):\n",
    "                        ans = cur_len\n",
    "                        res = cur\n",
    "                return\n",
    "            for nex in range(i, n):\n",
    "                if cur_len + nex - i + 1 < ans:\n",
    "                    # 不替换\n",
    "                    ele.append(target[i:nex+1])\n",
    "                    dfs(nex+1, False, ele, cur_len + nex - i + 1)\n",
    "                    ele.pop()\n",
    "                if not pre:\n",
    "                    # 替换\n",
    "                    if cur_len + 1 < ans:\n",
    "                        ele.append(str(nex - i + 1))\n",
    "                        dfs(nex+1, True, ele, cur_len + 1)\n",
    "                        ele.pop()\n",
    "        dfs(0, False, [], 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        import re\n",
    "        # 把长度一样找出来， 因为长度不一样缩写一定不一样\n",
    "        filter_dictionary = []\n",
    "        # target 所有缩写词\n",
    "        res = []\n",
    "        n = len(target)\n",
    "        for dis in dictionary:\n",
    "            if len(dis) == n:\n",
    "                filter_dictionary.append(dis)\n",
    "        if not filter_dictionary: return str(n)\n",
    "\n",
    "        # 每个缩写词的长度\n",
    "        def cmp(t):\n",
    "            return len(re.findall(r\"[0-9]+|[a-z]\", t))\n",
    "\n",
    "        # 回溯算法找出所有缩写\n",
    "        def helper(i, tmp):\n",
    "            if i == n:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                for j in range(i, n):\n",
    "                    num = str(j - i) if j - i > 0 else \"\"\n",
    "                    helper(j + 1, tmp + num + target[j])\n",
    "                helper(n, tmp + str(n - i))\n",
    "\n",
    "        helper(0, \"\")\n",
    "\n",
    "        # 判断abbr是否是word的缩写词\n",
    "        def vaild(abbr, word):\n",
    "            i = 0\n",
    "            j = 0\n",
    "            m = len(word)\n",
    "            n = len(abbr)\n",
    "            while i < m and j < n:\n",
    "                if abbr[j].isdigit():\n",
    "                    if abbr[j] == \"0\": return False\n",
    "                    num = 0\n",
    "                    while j < n and abbr[j].isdigit():\n",
    "                        num = num * 10 + int(abbr[j])\n",
    "                        j += 1\n",
    "                    i += num\n",
    "                else:\n",
    "                    if word[i] != abbr[j]:\n",
    "                        return False\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            return i == m and j == n\n",
    "\n",
    "        # 排序\n",
    "        res.sort(key=cmp)\n",
    "        for abbr in res:\n",
    "            if not any(vaild(abbr, word) for word in filter_dictionary):\n",
    "                return abbr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        import re\n",
    "        # 把长度一样找出来， 因为长度不一样缩写一定不一样\n",
    "        filter_dictionary = []\n",
    "        # target 所有缩写词\n",
    "        res = []\n",
    "        n = len(target)\n",
    "        for dis in dictionary:\n",
    "            if len(dis) == n:\n",
    "                filter_dictionary.append(dis)\n",
    "        if not filter_dictionary: return str(n)\n",
    "\n",
    "        # 每个缩写词的长度\n",
    "        def cmp(t):\n",
    "            return len(re.findall(r\"[0-9]+|[a-z]\", t))\n",
    "\n",
    "        # 回溯算法找出所有缩写\n",
    "        def helper(i, tmp):\n",
    "            if i == n:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                for j in range(i, n):\n",
    "                    num = str(j - i) if j - i > 0 else \"\"\n",
    "                    helper(j + 1, tmp + num + target[j])\n",
    "                helper(n, tmp + str(n - i))\n",
    "\n",
    "        helper(0, \"\")\n",
    "\n",
    "        # 判断abbr是否是word的缩写词\n",
    "        def vaild(abbr, word):\n",
    "            i = 0\n",
    "            j = 0\n",
    "            m = len(word)\n",
    "            n = len(abbr)\n",
    "            while i < m and j < n:\n",
    "                if abbr[j].isdigit():\n",
    "                    if abbr[j] == \"0\": return False\n",
    "                    num = 0\n",
    "                    while j < n and abbr[j].isdigit():\n",
    "                        num = num * 10 + int(abbr[j])\n",
    "                        j += 1\n",
    "                    i += num\n",
    "                else:\n",
    "                    if word[i] != abbr[j]:\n",
    "                        return False\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            return i == m and j == n\n",
    "\n",
    "        # 排序\n",
    "        res.sort(key=cmp)\n",
    "        for abbr in res:\n",
    "            if not any(vaild(abbr, word) for word in filter_dictionary):\n",
    "                return abbr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        n = len(target)\n",
    "        \n",
    "        ban = [False] * (1<<n)\n",
    "        for word in dictionary:\n",
    "            if len(word) != n:\n",
    "                continue\n",
    "            \n",
    "            # 11100\n",
    "            # 代表不能缩减为xxx2\n",
    "            state = 0 \n",
    "            for i in range(n):\n",
    "                if word[i] == target[i]:\n",
    "                    state += (1 << i)\n",
    "                       \n",
    "            s = state\n",
    "            while s:\n",
    "                ban[s] = True\n",
    "                s = (s - 1) & state\n",
    "            \n",
    "            ban[0] = True\n",
    "        \n",
    "        res = target\n",
    "        # print(ban)\n",
    "        for state in range(1<<n):\n",
    "            if ban[state]:\n",
    "                continue\n",
    "            \n",
    "            tmp = ''\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if (1<<i)&state == 0:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if cnt:\n",
    "                        tmp += str(cnt)  \n",
    "                    tmp += target[i]\n",
    "                    cnt = 0\n",
    "            if cnt:\n",
    "                tmp += str(cnt) \n",
    "            \n",
    "            if len(tmp) < len(res):\n",
    "                res = tmp\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def check(word: str, abbr: str) -> bool:\n",
    "            idx = jdx = 0\n",
    "            while jdx < len(abbr):\n",
    "                if abbr[jdx].isalpha():\n",
    "                    if idx >= len(word) or word[idx] != abbr[jdx]:\n",
    "                        return False\n",
    "                    idx += 1\n",
    "                    jdx += 1\n",
    "                else:\n",
    "                    r = jdx\n",
    "                    if abbr[r] == '0':\n",
    "                        return False\n",
    "                    while r < len(abbr) and abbr[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(abbr[jdx:r])\n",
    "                    idx += key\n",
    "                    jdx = r\n",
    "            return idx == len(word) and jdx == len(abbr)\n",
    "        def generate(word: str) -> str:\n",
    "            n = len(word)\n",
    "            ans = []\n",
    "            def dfs(idx, now):\n",
    "                bitcnt = 0\n",
    "                num = n-idx\n",
    "                while num:\n",
    "                    bitcnt += 1\n",
    "                    num //= 10\n",
    "                if len(ans) > 0 and len(now) + bitcnt >= len(ans[0]):\n",
    "                    return\n",
    "                if idx >= n:\n",
    "                    flag = True\n",
    "                    for item in dictionary:\n",
    "                        if check(item, now) == True:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        if len(ans) == 0:\n",
    "                            ans.append(now)\n",
    "                        elif len(ans[0]) > len(now):\n",
    "                            ans[0] = now\n",
    "                    return\n",
    "                for j in range(n-1, idx-1, -1):\n",
    "                    lenj = j-idx+1\n",
    "                    if not now or now[-1].isalpha():\n",
    "                        dfs(j+1, now+str(lenj))\n",
    "                    dfs(j+1, now+word[idx:j+1])\n",
    "            dfs(0, '')\n",
    "            return ans[0]\n",
    "\n",
    "        return generate(target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def check(word: str, abbr: str) -> bool:\n",
    "            if len(word) < len(abbr):\n",
    "                return False\n",
    "            idx = jdx = 0\n",
    "            while jdx < len(abbr):\n",
    "                if abbr[jdx].isalpha():\n",
    "                    if idx >= len(word) or word[idx] != abbr[jdx]:\n",
    "                        return False\n",
    "                    idx += 1\n",
    "                    jdx += 1\n",
    "                else:\n",
    "                    r = jdx\n",
    "                    if abbr[r] == '0':\n",
    "                        return False\n",
    "                    while r < len(abbr) and abbr[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(abbr[jdx:r])\n",
    "                    idx += key\n",
    "                    jdx = r\n",
    "                    if idx > len(word):\n",
    "                        return False\n",
    "            if idx == len(word):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        def generate(word: str) -> str:\n",
    "            n = len(word)\n",
    "            ans = []\n",
    "            def dfs(idx, now):\n",
    "                bitcnt = 0\n",
    "                num = n-idx\n",
    "                while num:\n",
    "                    bitcnt += 1\n",
    "                    num //= 10\n",
    "                if len(ans) > 0 and len(now) + bitcnt >= len(ans[0]):\n",
    "                    return\n",
    "                if idx >= n:\n",
    "                    flag = True\n",
    "                    for item in dictionary:\n",
    "                        if check(item, now) == True:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        if len(ans) == 0:\n",
    "                            ans.append(now)\n",
    "                        elif len(ans[0]) > len(now):\n",
    "                            ans[0] = now\n",
    "                    return\n",
    "                for j in range(n-1, idx-1, -1):\n",
    "                    lenj = j-idx+1\n",
    "                    if not now or now[-1].isalpha():\n",
    "                        dfs(j+1, now+str(lenj))\n",
    "                    dfs(j+1, now+word[idx:j+1])\n",
    "            dfs(0, '')\n",
    "\n",
    "            return ans[0]\n",
    "\n",
    "        return generate(target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def check(word: str, abbr: str) -> bool:\n",
    "            if len(word) < len(abbr):\n",
    "                return False\n",
    "            idx = jdx = 0\n",
    "            while jdx < len(abbr):\n",
    "                if abbr[jdx].isalpha():\n",
    "                    if idx >= len(word) or word[idx] != abbr[jdx]:\n",
    "                        return False\n",
    "                    idx += 1\n",
    "                    jdx += 1\n",
    "                else:\n",
    "                    r = jdx\n",
    "                    if abbr[r] == '0':\n",
    "                        return False\n",
    "                    while r < len(abbr) and abbr[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(abbr[jdx:r])\n",
    "                    idx += key\n",
    "                    jdx = r\n",
    "                    if idx > len(word):\n",
    "                        return False\n",
    "            if idx == len(word):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        def generate(word: str) -> str:\n",
    "            n = len(word)\n",
    "            ans = []\n",
    "            def dfs(idx, now):\n",
    "                bitcnt = 0\n",
    "                num = n-idx\n",
    "                while num:\n",
    "                    bitcnt += 1\n",
    "                    num //= 10\n",
    "                if len(ans) > 0 and len(now) + bitcnt >= len(ans[0]):\n",
    "                    return\n",
    "                if idx >= n:\n",
    "                    flag = True\n",
    "                    for item in dictionary:\n",
    "                        if check(item, now) == True:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        if len(ans) == 0:\n",
    "                            ans.append(now)\n",
    "                        elif len(ans[0]) > len(now):\n",
    "                            ans[0] = now\n",
    "                    return\n",
    "                for j in range(n-1, idx-1, -1):\n",
    "                    lenj = j-idx+1\n",
    "                    if not now or now[-1].isalpha():\n",
    "                        dfs(j+1, now+str(lenj))\n",
    "                    dfs(j+1, now+word[idx:j+1])\n",
    "            dfs(0, '')\n",
    "\n",
    "            return ans[0]\n",
    "\n",
    "        return generate(target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def generateAbbreviations(word):\n",
    "    res = []\n",
    "    length = len(word)\n",
    "    cur = []\n",
    "\n",
    "    def helper(cur_index, use_abbr, cur_length):\n",
    "        if cur_index == length:\n",
    "            res.append([cur_length, ''.join(cur)])\n",
    "            return\n",
    "        if use_abbr:\n",
    "            for i in range(cur_index, length):\n",
    "                cur.append(str(i - cur_index + 1))\n",
    "                helper(i + 1, False, cur_length + 1)\n",
    "                cur.pop()\n",
    "        cur.append(word[cur_index])\n",
    "        helper(cur_index + 1, True, cur_length + 1)\n",
    "        cur.pop()\n",
    "\n",
    "    helper(0, True, 0)\n",
    "    return res\n",
    "\n",
    "def validWordAbbreviation(word, abbr):\n",
    "    index = 0\n",
    "    cur_num = 0\n",
    "    for letter in abbr:\n",
    "        if letter.isalpha():\n",
    "            if cur_num > 0:\n",
    "                index = index + cur_num\n",
    "                cur_num = 0\n",
    "            if index >= len(word):\n",
    "                return False\n",
    "            if word[index] != letter:\n",
    "                return False\n",
    "            index += 1\n",
    "        else:\n",
    "            if not cur_num and letter == '0':\n",
    "                return False\n",
    "            cur_num = cur_num * 10 + int(letter)\n",
    "    if cur_num > 0:\n",
    "        index += cur_num\n",
    "    return index == len(word)\n",
    "\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        abbr_list = generateAbbreviations(target)\n",
    "        abbr_list.sort()\n",
    "        for _, abbr in abbr_list:\n",
    "            flag = True\n",
    "            for word in dictionary:\n",
    "                if validWordAbbreviation(word, abbr):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return abbr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        res = []\n",
    "        def check(word: str, abbr: str) -> bool:\n",
    "            idx = jdx = 0\n",
    "            while jdx < len(abbr):\n",
    "                if abbr[jdx].isalpha():\n",
    "                    if idx >= len(word) or word[idx] != abbr[jdx]:\n",
    "                        return False\n",
    "                    idx += 1\n",
    "                    jdx += 1\n",
    "                else:\n",
    "                    r = jdx\n",
    "                    if abbr[r] == '0':\n",
    "                        return False\n",
    "                    while r < len(abbr) and abbr[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(abbr[jdx:r])\n",
    "                    idx += key\n",
    "                    jdx = r\n",
    "            return idx == len(word) and jdx == len(abbr)\n",
    "        def generate(word: str) -> str:\n",
    "            n = len(word)\n",
    "            ans = []\n",
    "            def dfs(idx, now):\n",
    "                # bitcnt = 0\n",
    "                # num = n-idx\n",
    "                # while num:\n",
    "                #     bitcnt += 1\n",
    "                #     num //= 10\n",
    "                # if len(ans) > 0 and len(now) + bitcnt > len(ans[0]):\n",
    "                #     return\n",
    "                if idx == n:\n",
    "                    flag = True\n",
    "                    for item in dictionary:\n",
    "                        if check(item, now) == True:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        res.append(now)\n",
    "                    return\n",
    "                for j in range(idx, n):\n",
    "                    lenj = str(j-idx) if j-idx > 0 else ''\n",
    "                    dfs(j+1, now+lenj+word[j])\n",
    "                dfs(j+1, now+str(n-idx))\n",
    "            dfs(0, '')\n",
    "            res.sort(key=lambda x:(len(x), x))\n",
    "            # print(res)\n",
    "            return res[0]\n",
    "\n",
    "        return generate(target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:\n",
    "        res = []\n",
    "        # @lru_cache(None)\n",
    "        def check(word: str, abbr: str) -> bool:\n",
    "            idx = jdx = 0\n",
    "            while jdx < len(abbr):\n",
    "                if abbr[jdx].isalpha():\n",
    "                    if idx >= len(word) or word[idx] != abbr[jdx]:\n",
    "                        return False\n",
    "                    idx += 1\n",
    "                    jdx += 1\n",
    "                else:\n",
    "                    r = jdx\n",
    "                    if abbr[r] == '0':\n",
    "                        return False\n",
    "                    while r < len(abbr) and abbr[r].isdigit():\n",
    "                        r += 1\n",
    "                    key = int(abbr[jdx:r])\n",
    "                    idx += key\n",
    "                    jdx = r\n",
    "            return idx == len(word) and jdx == len(abbr)\n",
    "        def generate(word: str) -> str:\n",
    "            n = len(word)\n",
    "            ans = []\n",
    "            def dfs(idx, now):\n",
    "                bitcnt = 0\n",
    "                num = n-idx\n",
    "                while num:\n",
    "                    bitcnt += 1\n",
    "                    num //= 10\n",
    "                if len(ans) > 0 and len(now) + bitcnt > len(ans[0]):\n",
    "                    return\n",
    "                if idx == n:\n",
    "                    flag = True\n",
    "                    for item in dictionary:\n",
    "                        if check(item, now) == True:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        res.append(now)\n",
    "                    return\n",
    "                for j in range(idx, n):\n",
    "                    lenj = str(j-idx) if j-idx > 0 else ''\n",
    "                    dfs(j+1, now+lenj+word[j])\n",
    "                dfs(j+1, now+str(n-idx))\n",
    "            dfs(0, '')\n",
    "            res.sort(key=lambda x:(len(x), x))\n",
    "            # print(res)\n",
    "            return res[0]\n",
    "\n",
    "        return generate(target)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
